package demo;

import java.util.Comparator;
import java.util.PriorityQueue;

public class Code02_Heap {

	static class MyMaxHeap {

		private int[] heap;
		private final int limit;//堆的总容量
		private int usedSize;

		public MyMaxHeap(int limit){
			this.heap = new int[limit];
			this.limit = limit;
			this.usedSize = 0;
		}

		public boolean isEmpty(){
			return this.usedSize == 0;
		}

		public boolean isFull(){
			return this.usedSize == this.limit;
		}

		public void push(int value){
			if (this.usedSize == limit) {
				throw new RuntimeException("heap is full");
			}
			this.heap[this.usedSize] = value;
			heapInsert(this.usedSize);
			this.usedSize++;
		}

		public static void swap(int[] arr,int i,int j){
			int tmp = arr[i];
			arr[i] = arr[j];
			arr[j] = tmp;
		}

		public void heapInsert(int child){

			while(this.heap[child]>this.heap[(child - 1) / 2]){
				//如果比父亲大就交换
				swap(this.heap,child,(child - 1) / 2);
				child = (child - 1) / 2;
			}
		}

		public int pop(){
			if(isEmpty()) {
				throw new RuntimeException("堆为空,不能删除");
			}
			int ans = this.heap[0];
			//堆顶元素与最后一个元素交换
			swap(this.heap,0,this.usedSize-1);
			//向下调整0下标
			this.usedSize--;
			heapIfy(0,this.usedSize);
			return ans;
		}

		public void heapIfy(int parent,int heapSize){
			int child = 2*parent + 1;
			while(child < heapSize){
				//选错左右孩子较大的
				if(child+1 < heapSize && this.heap[child]<this.heap[child+1]){
					child = child+1;
				}
				if(this.heap[parent]>=this.heap[child]){
					break;
				}
				swap(this.heap,parent,child);
				parent = child;
				child = 2* parent + 1;
			}
		}

	}

	public static class RightMaxHeap {
		private int[] arr;
		private final int limit;
		private int size;

		public RightMaxHeap(int limit) {
			arr = new int[limit];
			this.limit = limit;
			size = 0;
		}

		public boolean isEmpty() {
			return size == 0;
		}

		public boolean isFull() {
			return size == limit;
		}

		public void push(int value) {
			if (size == limit) {
				throw new RuntimeException("heap is full");
			}
			arr[size++] = value;
		}

		public int pop() {
			int maxIndex = 0;
			for (int i = 1; i < size; i++) {
				if (arr[i] > arr[maxIndex]) {
					maxIndex = i;
				}
			}
			int ans = arr[maxIndex];
			arr[maxIndex] = arr[--size];
			return ans;
		}

	}

	public static class MyComparator implements Comparator<Integer> {

		@Override
		public int compare(Integer o1, Integer o2) {
			return o2 - o1;
		}

	}

	public static void main(String[] args) {
		int value = 1000;
		int limit = 100;
		int testTimes = 1000000;
		for (int i = 0; i < testTimes; i++) {
			int curLimit = (int) (Math.random() * limit) + 1;
			MyMaxHeap my = new MyMaxHeap(curLimit);
			RightMaxHeap test = new RightMaxHeap(curLimit);
			int curOpTimes = (int) (Math.random() * limit);
			for (int j = 0; j < curOpTimes; j++) {
				if (my.isEmpty() != test.isEmpty()) {
					System.out.println("Oops!");
				}
				if (my.isFull() != test.isFull()) {
					System.out.println("Oops!");
				}
				if (my.isEmpty()) {
					int curValue = (int) (Math.random() * value);
					my.push(curValue);
					test.push(curValue);
				} else if (my.isFull()) {
					if (my.pop() != test.pop()) {
						System.out.println("Oops!");
					}
				} else {
					if (Math.random() < 0.5) {
						int curValue = (int) (Math.random() * value);
						my.push(curValue);
						test.push(curValue);
					} else {
						if (my.pop() != test.pop()) {
							System.out.println("Oops!");
						}
					}
				}
			}
		}
		System.out.println("finish!");
	}

}